package com.atguigu.structures;

public class BinaryTreeExample {

    public static void main(String[] args) {
        Tree root = new Tree(8);
        root.left = new Tree(3);
        root.left.left = new Tree(1);
        root.left.right = new Tree(6);
        root.left.right.left = new Tree(4);
        root.left.right.right = new Tree(7);
        root.right = new Tree(10);
        root.right.right = new Tree(14);
        root.right.right.left = new Tree(13);

        preOrder(root);
        System.out.println("-----------------------");
        inOrder(root);
        System.out.println("-----------------------");
        afterOrder(root);
        System.out.println(searchBinaryTree(root, 15));
    }

    public static class Tree {
        public int value;
        public Tree left;
        public Tree right;

        public Tree(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

    }

    /**
     * 先序遍历：中左右
     */
    public static void preOrder(Tree node) {
        System.out.println(node.value);
        if (node.left != null) preOrder(node.left);
        if (node.right != null) preOrder(node.right);
    }

    /**
     * 中序遍历：左中右
     *
     * @param node
     */
    public static void inOrder(Tree node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.value);
            inOrder(node.right);
        }
    }

    /**
     * 后序遍历 左右中
     *
     * @param node
     */
    public static void afterOrder(Tree node) {
        if (node != null) {
            afterOrder(node.left);
            afterOrder(node.right);
            System.out.println(node.value);
        }
    }

    /**
     * 二叉树查找
     *
     * @param node
     * @param value
     * @return
     */
    public static boolean searchBinaryTree(Tree node, int value) {
        if (node==null) return false;
        if (node.value == value) return true;
        if (value<node.value) {
            return searchBinaryTree(node.left, value);
        } else {
            return searchBinaryTree(node.right,value);
        }
    }
}
